<!DOCTYPE html>
    <html>
    <head>
        <meta charset="UTF-8">
        <title>四平方和</title>
        <style>
</style>
        
        <link rel="stylesheet" href="https://cdn.jsdelivr.net/gh/Microsoft/vscode/extensions/markdown-language-features/media/markdown.css">
<link rel="stylesheet" href="https://cdn.jsdelivr.net/gh/Microsoft/vscode/extensions/markdown-language-features/media/highlight.css">
<style>
            body {
                font-family: -apple-system, BlinkMacSystemFont, 'Segoe WPC', 'Segoe UI', system-ui, 'Ubuntu', 'Droid Sans', sans-serif;
                font-size: 14px;
                line-height: 1.6;
            }
        </style>
        <style>
.task-list-item { list-style-type: none; } .task-list-item-checkbox { margin-left: -20px; vertical-align: middle; }
</style>
        
        
        
    </head>
    <body class="vscode-light">
        <h1 id="四平方和">四平方和</h1>
<h1 id="lc-279-perfect-squares">LC 279. Perfect Squares</h1>
<ul>
<li><a href="https://leetcode.com/problems/perfect-squares/">https://leetcode.com/problems/perfect-squares/</a></li>
</ul>
<h2 id="1-dp-解法类似于求最少数量硬币的兑换">1. dp 解法，类似于求最少数量硬币的兑换</h2>
<p>提交以后会超时</p>
<pre><code class="language-python"><div><span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">Solution</span>:</span>
    <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">numSquares</span><span class="hljs-params">(self, n: int)</span> -&gt; int:</span>
        <span class="hljs-keyword">if</span> n &lt; <span class="hljs-number">1</span>:
            <span class="hljs-keyword">return</span> <span class="hljs-number">0</span>
        dp = [float(<span class="hljs-string">'inf'</span>) <span class="hljs-keyword">for</span> i <span class="hljs-keyword">in</span> range(n + <span class="hljs-number">1</span>)]
        dp[<span class="hljs-number">0</span>] = <span class="hljs-number">0</span>
        <span class="hljs-keyword">for</span> i <span class="hljs-keyword">in</span> range(<span class="hljs-number">1</span>, n + <span class="hljs-number">1</span>):
            <span class="hljs-keyword">for</span> j <span class="hljs-keyword">in</span> range(<span class="hljs-number">1</span>, int(i ** <span class="hljs-number">0.5</span>) + <span class="hljs-number">1</span>):
                dp[i] = min(dp[i], dp[i - j * j] + <span class="hljs-number">1</span>)
        <span class="hljs-keyword">return</span> dp[n]
</div></code></pre>
<h2 id="2-bfs方法">2. bfs方法</h2>
<pre><code class="language-python"><div><span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">Solution</span>:</span>
    <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">numSquares</span><span class="hljs-params">(self, n: int)</span> -&gt; int:</span>
        <span class="hljs-keyword">if</span> n &lt;= <span class="hljs-number">0</span>:
            <span class="hljs-keyword">return</span> <span class="hljs-number">0</span>
        perfectsquals = []
        bfs_stack = []
        <span class="hljs-keyword">for</span> i <span class="hljs-keyword">in</span> range(<span class="hljs-number">1</span>, n+<span class="hljs-number">1</span>):
            <span class="hljs-keyword">if</span> i * i &gt; n:
                <span class="hljs-keyword">break</span>
            perfectsquals.append(i*i)
            bfs_stack.append((i*i, <span class="hljs-number">1</span>))
        
        <span class="hljs-keyword">if</span> perfectsquals[<span class="hljs-number">-1</span>] == n:
            <span class="hljs-keyword">return</span> <span class="hljs-number">1</span>
        
        visited = [<span class="hljs-literal">False</span>] * (n+<span class="hljs-number">1</span>)
        <span class="hljs-keyword">while</span> bfs_stack:
            bfs_node, bfs_level = bfs_stack.pop(<span class="hljs-number">0</span>)
            <span class="hljs-keyword">for</span> ps <span class="hljs-keyword">in</span> perfectsquals:
                bfs_next = ps + bfs_node
                <span class="hljs-keyword">if</span> bfs_next == n:
                    <span class="hljs-keyword">return</span> bfs_level+<span class="hljs-number">1</span>
                <span class="hljs-keyword">elif</span> bfs_next &gt; n:
                    <span class="hljs-keyword">break</span>
                <span class="hljs-keyword">elif</span> visited[bfs_next]:
                    <span class="hljs-keyword">continue</span>
                <span class="hljs-keyword">else</span>:
                    visited[bfs_next] = <span class="hljs-literal">True</span>
                    bfs_stack.append((bfs_next, bfs_level+<span class="hljs-number">1</span>))
                    
        <span class="hljs-keyword">return</span> <span class="hljs-number">0</span>
</div></code></pre>
<h2 id="3-数学方法">3. 数学方法。</h2>
<p>四数平方和定理还有一个重要的推论：满足四数平方和定理的数 n = 4**X * (8a*b) （四个整数的情况）。就是说如果一个正整数不满足这个形式，则它就可以写成三个正整数的平方和。</p>
<pre><code class="language-python"><div><span class="hljs-keyword">import</span> math

<span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">Solution</span>:</span>
    <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">numSquares</span><span class="hljs-params">(self, n: int)</span> -&gt; int:</span>
        <span class="hljs-keyword">if</span> n &lt; <span class="hljs-number">1</span>:
            <span class="hljs-keyword">return</span> <span class="hljs-number">0</span>
            
        n2 = int(sqrt(n))
        coins = [i*i <span class="hljs-keyword">for</span> i <span class="hljs-keyword">in</span> range(<span class="hljs-number">1</span>, n2+<span class="hljs-number">1</span>)]
        <span class="hljs-keyword">if</span> n <span class="hljs-keyword">in</span> coins:
            <span class="hljs-keyword">return</span> <span class="hljs-number">1</span>
        
        n0 = n 
        <span class="hljs-keyword">while</span> n0 % <span class="hljs-number">4</span> == <span class="hljs-number">0</span>:
            n0 = n0 // <span class="hljs-number">4</span>
        <span class="hljs-keyword">if</span> n0 % <span class="hljs-number">8</span> == <span class="hljs-number">7</span>:
            <span class="hljs-keyword">return</span> <span class="hljs-number">4</span>
        
        <span class="hljs-keyword">for</span> coin <span class="hljs-keyword">in</span> coins:
            <span class="hljs-keyword">if</span> (n - coin) <span class="hljs-keyword">in</span> coins:
                <span class="hljs-keyword">return</span> <span class="hljs-number">2</span>
            
        <span class="hljs-keyword">return</span> <span class="hljs-number">3</span>
</div></code></pre>

    </body>
    </html>